package LearnAlgorithm.c_递归and查找排序;

import java.util.Arrays;

public class u乱序数组是否包含另一个乱序数组 {
	public static void main(String[] args) {
		String s1 = "abc";
		String s2 = "qwertyuioabc";
		System.out.println(binaryCheck(s1, s2));;
	}
	
	/**
	 * 快速排序
	 * 二分查找
	 * O(NlogN)
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static boolean binaryCheck(String s1, String s2) {
		char[] s2Chars = s2.toCharArray();//字符串	转	字符数组
		Arrays.sort(s2Chars);//字符数组快速排序
		for (int i = 0; i < s1.length(); i++) {
			char a = s1.charAt(i);//取s1当前索引i的字符a
			if (Arrays.binarySearch(s2Chars, a) < 0) {//使用二分查找有序数组提高查找效率
				return false;
			}
		}
		return true;//都存在，返回true
	}
	
	/**
	 * 暴力循环解法
	 * O(N^2)
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static boolean forceCheck(String s1, String s2) {
		for (int i = 0; i < s1.length(); i++) {
			char a = s1.charAt(i);//取s1当前索引i的字符a
			if (s2.indexOf(a) == -1) {//字符a在s2中查找，是否存在，不存在indexOf返回-1
				return false;//只要有一个字符不存在，就不可能包含了，直接返回false
			}
		}
		return true;//都存在，返回true
	}
	
	
}
